package zoran.wang.day14;

import org.junit.Test;

import java.util.LinkedList;

/**
 * 吃苹果,用回溯算法试试
 *
 * @author wangzhuo
 * @time 2025-04-15-22:05
 */
public class EatApplesTest2 {

    // 苹果总数
    private int total;
    // 一天最多能吃的苹果个数
    private int maxInOneDay;
    // 快乐值数组
    private int[] happyArray;
    // 记录快乐值
    private int happyValue;
    // 收集结果
    private int res;

    public int eatApple(int n, int m, int[] a) {

        this.total = n;
        this.maxInOneDay = m;
        this.happyArray = a;
        this.happyValue = 0;
        this.res = 0;

        backtrack(total);

        return res;
    }

    private void backtrack(int cur) {

        // base case
        if (cur < 0) return;
        // 到达目标叶子节点
        if (cur == 0) {
            // 比较最大快乐值
            System.out.println("快乐值:" + happyValue);
            res = Math.max(res, happyValue);
            return;
        }

        // 遍历选择列表 happyArray[0,length-1]
        for (int i = 0; i < happyArray.length; i++) {

            // 这天吃掉的苹果数量
            int count = i + 1;

            happyValue += happyArray[i];
            backtrack(cur - count);

            happyValue -= happyArray[i];
        }

    }

    private int sum(LinkedList<Integer> list) {

        int sum = 0;
        for (Integer i : list) {
            sum += i;
        }
        return sum;
    }

    @Test
    public void test() {
        int result = eatApple(4, 3, new int[]{1, 60, 100});
        System.out.println("result = " + result);
    }
}
